public class try2 {
    class Solution {
        public int[] searchRange(int[] nums, int target) {
            int x = binarySearchLeftmost(nums, target);
            if (x == -1) {
                return new int[]{-1, -1};
            }
            return new int[]{x, binarySearchRightmost(nums, target)};
        }
    }

    public static int binarySearchLeftmost(int a[], int target) {
        int first = 0;
        int end = a.length - 1;
        int candidate = -1;
        while (first <= end) {
            int mid = (first + end) >>> 1;
            if (target > a[mid]) {
                first = mid + 1;
            } else if (target < a[mid]) {
                end = mid - 1;
            } else {
                candidate = mid;
                end = mid - 1;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
            }
        }
        return candidate;
    }

    public static int binarySearchRightmost(int a[], int target) {
        int first = 0;
        int end = a.length - 1;
        int candidate = -1;
        while (first <= end) {
            int mid = (first + end) >>> 1;
            if (target > a[mid]) {
                first = mid + 1;
            } else if (target < a[mid]) {
                end = mid - 1;
            } else {
                candidate = mid;
                first = mid + 1;//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
            }
        }
        return candidate;
    }
}
